package com.fjl.list.leetcode160;

import com.fjl.list.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description
 * @Author: 01195
 * @Date: 2025/2/17 11:28
 */
public class IntersectionNode {

    public static void main(String[] args) {

    }

    // 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
    // 第一种方法，遍历一个，存起来，如果有相同的，就返回
    private ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        List<ListNode> list = new ArrayList<>();
        ListNode p1 = headA;
        ListNode p2 = headB;
        while (p1 != null) {
            list.add(p1);
            p1 = p1.next;
        }
        while (p2 != null) {
            if (list.contains(p2)) {
                return p2;
            }
            list.add(p2);
            p2 = p2.next;
        }
        return null;
    }

    // 第二种方案：
    // 难点在于，由于两条链表的长度可能不同，两条链表之间的节点无法对应
    // 解决这个问题的关键是，通过某些方式，让 p1 和 p2 能够同时到达相交节点 c1。
    //所以，我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。
    //如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1

    // 那你可能会问，如果说两个链表没有相交点，是否能够正确的返回 null 呢？
    //这个逻辑可以覆盖这种情况的，相当于 c1 节点是 null 空指针嘛，可以正确返回 null。
    private ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        ListNode p1 = headA;
        ListNode p2 = headB;
        while (p1 != p2) {
            // p1 走一步，如果走到 A 链表末尾，转到 B 链表
            if (p1 == null) {
                p1 = headB; // 这两步操作是互斥的，不能既指向另一个链表，又接着next,这样相当于走了两步
            } else {
                p1 = p1.next;
            }

            // p2 走一步，如果走到 B 链表末尾，转到 A 链表
            if (p2 == null) {
                p2 = headA;
            } else {
                p2 = p2.next;
            }
        }
        return p1;
    }
}
